/**
 * //A transformation sequence from word beginWord to word endWord using a
 * //dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
 * //
 * //
 * //
 * // Every adjacent pair of words differs by a single letter.
 * // Every si for 1 <= i <= k is in wordList. Note that beginWord does not need
 * //to be in wordList.
 * // sk == endWord
 * //
 * //
 * // Given two words, beginWord and endWord, and a dictionary wordList, return
 * //the number of words in the shortest transformation sequence from beginWord to
 * //endWord, or 0 if no such sequence exists.
 * //
 * //
 * // Example 1:
 * //
 * //
 * //Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog",
 * //"lot","log","cog"]
 * //Output: 5
 * //Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -
 * //> "dog" -> cog", which is 5 words long.
 * //
 * //
 * // Example 2:
 * //
 * //
 * //Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog",
 * //"lot","log"]
 * //Output: 0
 * //Explanation: The endWord "cog" is not in wordList, therefore there is no
 * //valid transformation sequence.
 * //
 * //
 * //
 * // Constraints:
 * //
 * //
 * // 1 <= beginWord.length <= 10
 * // endWord.length == beginWord.length
 * // 1 <= wordList.length <= 5000
 * // wordList[i].length == beginWord.length
 * // beginWord, endWord, and wordList[i] consist of lowercase English letters.
 * // beginWord != endWord
 * // All the words in wordList are unique.
 * //
 * //
 * // Related Topics 广度优先搜索 哈希表 字符串 👍 1075 👎 0
 */

package com.xixi.basicAlgroithms.BreadthWidthFirstSearch;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

public class ID00127WordLadder {
    public static void main(String[] args) {

        Solution solution = new ID00127WordLadder().new Solution();
        System.out.println(solution.ladderLength("hit", "cog", Arrays.asList(new String[]{"hot", "dot", "dog", "lot", "log", "cog"})));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        boolean[] visited = null;

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {

            //防止成环
            visited = new boolean[wordList.size()];

            Queue<String> nextWordQueue = new ArrayDeque<String>();

            nextWordQueue.add(beginWord);
            int thisStepSize = 1;
            int steps = 1;
            int nextStepSize = 0;

            while (!nextWordQueue.isEmpty()) {
                String thisWord = nextWordQueue.poll();
                for (int i = 0; i < wordList.size(); i++) { //遍历每个单词，看看是否能跳
                    if (!visited[i] && ableToJump(thisWord, wordList.get(i))) { //没被浏览过，并且能跳
                        if (wordList.get(i).equalsIgnoreCase(endWord)) { //找到了
                            return steps + 1; //因为未开始下一层
                        }
                        nextWordQueue.add(wordList.get(i));
                        visited[i] = true;
                        nextStepSize++;

                    }

                }

                thisStepSize--;
                if (thisStepSize == 0) { //本层已经遍历结束
                    thisStepSize = nextStepSize; //进阶到下一层
                    nextStepSize = 0;
                    steps++;
                }

            }
            return 0; //没找到


        }


        //能否跳到下一个单词,如果只有一位不同，就可以跳,小于或超过一位都不行
        public boolean ableToJump(String startWord, String nextWord) {
            int differenceNum = 0;
            char[] startChar = startWord.toCharArray();
            char[] nextChar = nextWord.toCharArray();

            for (int i = 0; i < startWord.length(); ++i) {
                if (startChar[i] != nextChar[i]) {
                    ++differenceNum;
                }
            }

            return differenceNum == 1;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}